home *** CD-ROM | disk | FTP | other *** search
/ Collection of Tools & Utilities / Collection of Tools and Utilities.iso / archiver / huff_sc.zip / UNHUF.C < prev    next >
C/C++ Source or Header  |  1991-04-25  |  15KB  |  492 lines
  1. /*******************************************************************************
  2. *                                                                              *
  3. * UNHUF.C   by Shaun Case   April 1991                                         *
  4. *                                                                              *
  5. * Written in Borland C++ 2.0 under MS-DOS 3.3                                  *
  6. *                                                                              *
  7. * Decompresses a single file encoded with companion program HUF,               *
  8. * which uses Huffman encoding.                                                 *
  9. *                                                                              *
  10. * This program is in the public domain.                                        *
  11. *                                                                              *
  12. * atman%ecst.csuchico.edu@RELAY.CS.NET                                         *
  13. *                                                                              *
  14. *                                                                              *
  15. *******************************************************************************/
  16.  
  17. #include <stdio.h>
  18. #include <math.h>
  19.  
  20. #define FALSE 0
  21. #define TRUE !FALSE
  22. #define MAX_DECODE_TABLE_SIZE 520       /* 512 should be enough           */
  23.  
  24.  
  25. /* uncomment the next line to see the decode table at runtime. */
  26.  
  27. /*
  28. #define DEBUG
  29. */
  30.  
  31.  
  32. /* uncomment the next line to only uncompress the exact number of bytes   */
  33. /* that were originally encoded.  If it is not defined, the routine will  */
  34. /* faster, but will generate up to 8 extra bytes at the end of the        */
  35. /* decompressed data.                                                     */
  36.  
  37. #define EXACT
  38.  
  39.  
  40. typedef struct decode_table_element {   /* template for decode table element (wow)  */
  41.     unsigned char letter;               /* which character to decode to             */
  42.     char spare;                         /* force 16-bit word alignment              */
  43.     short left;                         /* index of lower left element from tree    */
  44.     short right;                        /* index of lower right element from tree   */
  45. }decode_table_element;
  46.  
  47.  
  48. short array_max_index;                  /* max number of elements in array (to be   */
  49.                                         /* determined in create_decode_table() )    */
  50.  
  51. unsigned long  total;                   /* total number of unencoded bytes          */
  52. FILE *infile;                           /* file ptr to SYSTEM.HUF (compressed)      */
  53. FILE *outfile;                          /* file ptr to SYSTEM.UNH (decompressed)    */
  54. char *infilename;                       /* name of the input file                   */
  55. char origfilename[13];                  /* name of the original file                */
  56.  
  57. struct decode_table_element             /* array implementation of huffman tree     */
  58.     decode_table[MAX_DECODE_TABLE_SIZE];
  59.  
  60. /******
  61.  *
  62.  * Datafile:  All 16/32 bit quantities in Intel byte ordering
  63.  *
  64.  *  13 bytes    : original filename (8.3 + '\0')
  65.  *  16 bits     : number of array elements needed, N (N == 511 means 512 array
  66.  *                elements -> 0..511)
  67.  *  32 bits     : size of uncompressed original data in bytes
  68.  *  N * 6 bytes : Array elements in order 0 .. N
  69.  *                struct decode_table_element {
  70.  *                     char letter;      8 bits
  71.  *                     char spare;       8 bits
  72.  *                     short left;      16 bits
  73.  *                     short right;     16 bits
  74.  *                 }
  75.  *  <?>          : compressed data, effectively a bit stream
  76.  *
  77.  ******/
  78.  
  79.  
  80. int main(int argc, char **argv)
  81. {
  82.     short read_header(void);                /* prototype */
  83.     void show_bit_sequences(short index);   /* prototype */
  84.     short uncompress(void);                 /* prototype */
  85.  
  86.     if (argc != 2) {                        /* check command line argument validity  */
  87.         puts("'unhuf file' decodes file.");
  88.         return 1;
  89.     }
  90.     puts("Unhuf by Shaun Case, 1991, public domain");
  91.  
  92.     infilename=argv[1];
  93.  
  94.  
  95.     if (read_header() != 0)                 /* read in file name, size, decode table */
  96.         return 1;
  97.  
  98. #ifdef DEBUG
  99.     show_bit_sequences(0);
  100. #endif
  101.  
  102.     if (uncompress() != 0)                  /* uncompress the data & write to file   */
  103.         return 1;
  104.  
  105.     fclose(infile);
  106.  
  107.     return 0;
  108.  
  109. }
  110.  
  111. /*
  112.  * read in the original filename, size, and decode table
  113.  *
  114.  */
  115.  
  116. short read_header(void)
  117. {
  118.     if ((infile=fopen(infilename, "rb")) == NULL)        /* open file           */
  119.     {
  120.         printf("Unable to open %s\n", infilename);
  121.         return 1;
  122.     }
  123.  
  124.  
  125.     if (                                                 /* get original name   */
  126.           fread((void *)origfilename, 1, 13, infile)
  127.           < 13
  128.        )
  129.     {
  130.         printf("Unable to read original filename from %s\n", infilename);
  131.         fclose(infile);
  132.         return 1;
  133.     }
  134.  
  135.                                                          /* get length of decode table */
  136.     if (
  137.           fread((void *)&array_max_index, sizeof(short), 1, infile)
  138.           < 1
  139.        )
  140.     {
  141.         printf("Unable to read number of array elements from %s\n", infilename);
  142.         fclose(infile);
  143.         return 1;
  144.     }
  145.  
  146.         if (                                             /* get filesize in bytes */
  147.               fread((void *)&total, sizeof(unsigned long), 1, infile)
  148.             < 1
  149.        )
  150.     {
  151.         printf("Unable to read original byte count from %s\n", infilename);
  152.         fclose(infile);
  153.         return 1;
  154.     }
  155.  
  156.     printf("Decoding %ld bytes to %s.\n", total, origfilename);
  157.     printf("Decode table contains %d elements.\n",array_max_index + 1);
  158.  
  159.     if (                                                /* get decode table        */
  160.           fread((void *)decode_table, sizeof(decode_table_element), array_max_index + 1, infile)
  161.           < (array_max_index + 1)
  162.        )
  163.     {
  164.         printf("Unable to read decode table from %s\n", infilename);
  165.         fclose(infile);
  166.         return 1;
  167.     }
  168.  
  169.     return 0;
  170. }
  171.  
  172. #ifdef DEBUG
  173. short seq_len=0;  /* routine is recursive, needs global storage  */
  174.                   /* length of current bit sequence              */
  175.                   /* this should probably be static inside sbs() */
  176.  
  177.  
  178. /*
  179.  * display the bit sequences that represent each character.
  180.  * useful for debugging.
  181.  *
  182.  */
  183.  
  184. void show_bit_sequences(short index)
  185. {
  186.  
  187.     static short temp_index=0;
  188.     static char bit_sequence[16];       /* where to build the huffman bit sequence  */
  189.  
  190.     if (decode_table[index].left != 0)  /* if we are not at a leaf, go left         */
  191.     {
  192.         bit_sequence[seq_len++]='1';
  193.         show_bit_sequences(decode_table[index].left);
  194.         seq_len--;
  195.     }
  196.                                         /* returned from going left, now try right  */
  197.     if (decode_table[index].right != 0)
  198.     {
  199.         bit_sequence[seq_len++]='0';    /* if we are not at a leaf, go right        */
  200.         show_bit_sequences(decode_table[index].right);
  201.         seq_len--;
  202.     }
  203.  
  204.     if (decode_table[index].left != NULL)    /* we are at an interior node going back up */
  205.         return;
  206.  
  207.     /* we are at a leaf, therefore we have a complete bit sequence built            */
  208.  
  209.     bit_sequence[seq_len] = 0;          /* append teriminating NULL to string       */
  210.  
  211.     printf("[%3d] %3d == %16s == %3d\n", temp_index, decode_table[index].letter, bit_sequence, seq_len);
  212.     temp_index++;
  213. }
  214.  
  215. #endif
  216.  
  217. /*
  218.  * all the fputc() calls are unrolled for speed.
  219.  *
  220.  */
  221.  
  222. short uncompress(void)
  223. {
  224.  
  225.     /* tcc68 can assign 7 register variables */
  226.  
  227.     register short index         = 0;               /* "ptr" to "node" in "tree"        */
  228.                                                     /* actually an array index          */
  229.     register unsigned unsigned int buffer = 0;      /* 8 bit buffer                     */
  230.     register unsigned short fastleft;